
//1146.快照数组
class SnapshotArray {
    int count;
    unordered_map<int,vector<pair<int,int>>> nums;

public:
    SnapshotArray(int length) {
        count=0;
    }
    
    void set(int index, int val) {
        nums[index].push_back({count,val});
    }
    
    int snap() {
        return count++;
    }
    
    int get(int index, int snap_id) {
        vector<pair<int,int>>& tmp=nums[index];
        auto pos=ranges::upper_bound(tmp,snap_id,{},[](auto& e){return e.first;})-tmp.begin()-1;
        if(pos<0) return 0;

        return tmp[pos].second;
    }
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */